#include <iostream>
#include <vector>

using namespace std;

class Solution {
	int max_profit(vector<int> &prices, int left, int i, vector<vector<int>> &dp)
	{
		if (left == 0 || i < 0) {
			return 0;
		}

		if (dp[i][left] != -1) {
			return dp[i][left];
		}

		int ans = max_profit(prices, left, i - 1, dp);
		for (int j = 0; j < i; j++) {
			ans = max(ans, max_profit(prices, left - 1, j, dp) + prices[i] - prices[j]);
		}
		return dp[i][left] = ans;
	}

	int max_profit(vector<int> &prices, int t)
	{
		prices.insert(prices.begin(), 0);
		vector<vector<int>> dp(prices.size(), vector<int>(t + 1, 0));
		for (int i = 1; i < prices.size(); i++) {
			for (int k = 1; k <= t; k++) {
				dp[i][k] = dp[i - 1][k];
				for (int j = 1; j < i; j++) {
					dp[i][k] = max(dp[i][k], dp[j][k - 1] + prices[i] - prices[j]);
				}
			}
		}
		return dp[prices.size() - 1][t];
	}

	int max_profit2(vector<int> &prices, int t)
	{
		int best = 0;
		prices.insert(prices.begin(), 0);
		vector<vector<int>> dp(prices.size(), vector<int>(t + 1, 0));
		for (int k = 1; k <= t; k++) {
			for (int i = 1; i < prices.size(); i++) {
                                dp[i][k] = dp[i - 1][k];
                                for(int j = 1; j < i; j++){
                                        dp[i][k] = max(dp[i][k], dp[j][k - 1] + prices[i] - prices[j]);
                                }
                        }
		}
		return dp[prices.size() - 1][t];
	}

        int max_profit3(vector<int> &prices, int t)
        {
                int best = 0;
                prices.insert(prices.begin(), 0);
                vector<vector<int>> dp(prices.size(), vector<int>(t + 1, 0));
                for (int k = 1; k <= t; k++) {
                        best = dp[1][k] - prices[1];
                        for (int i = 1; i < prices.size(); i++) {
                                dp[i][k] = dp[i - 1][k];
                                dp[i][k] = max(dp[i][k], best + prices[i]);
                                best = max(best, dp[i][k - 1] - prices[i]);
                        }
                }
                return dp[prices.size() - 1][t];
        }
    public:
	int maxProfit(int k, vector<int> &prices)
	{
		vector<vector<int>> dp(prices.size(), vector<int>(k + 1, -1));
		//return max_profit(prices, k, prices.size() - 1, dp);
		return max_profit3(prices, k);
	}
};

int main()
{
	vector<int> prices = { 2, 4, 1 };
	int k = 2;
	cout << Solution().maxProfit(k, prices) << endl;
	return 0;
}